In the context of integrated circuit (IC) design, a "layout" is a set of geometric patterns, typically in the form of polygons, which specify the size and location of different types of material used to create semiconductor devices and electrical connections between the devices during the fabrication of an IC. For example, a diffusion window on an IC may be represented in a layout by one or more polygons which are interpreted by a fabrication facility to mean "diffusion layer geometry." Other layers of material and features, such as contacts and vias, may be similarly represented in an IC layout. The polygons in an IC layout must satisfy a set of design rules that defines minimum sizes for certain types of material as well as minimum spacing requirements between different types of material. The set of design rules also specifies size and spacing requirements for other layout features such as contacts.
Sometimes, IC layouts are drawn by hand using a computer aided design (CAD) system. This approach is often adequate for designing IC layouts having a relatively small number of devices. However, modern fabrication technology allows several million transistors to be placed on a single silicon substrate. Drawing an IC layout by hand that contains millions of transistors is not practical because of the excessive time required, even if standardized cells are used to reduce the number of individual transistors that must be drawn. Consequently, various computer-based IC layout design tools have been developed to automate the generation of IC layouts. Two types of layout design tools include leaf cell compaction tools and leaf cell synthesis tools. In the context of IC layouts, the term "leaf cell" refers to a group of transistors, typically from two to several hundred, that together perform a specific function, such as a NAND logical operation or storing a bit of information.
Leaf cell compaction tools are used to reduce the size of an existing IC layout. Most leaf cell compaction tools compact a layout in either the vertical or horizontal direction by eliminating extra space between polygons. "Full" compaction is sometimes provided by first compressing a layout in the horizontal direction and then compressing the layout in the vertical direction. However, most leaf cell compaction tools are also able to adjust the coordinates of the polygon points in an IC layout until they meet the design rules for a particular fabrication process, making them helpful for porting an existing layout from a current set of design rules to a new set of design rules. Despite the benefits of leaf cell compaction tools, even a compacted layout is larger than comparable hand-drawn cells because compaction is generally a one-dimensional process. Also, compaction tools maintain the existing layout structure even though non-linear changes in design rules (e.g. proportionately increased metal overlap around a contact) often cause human layout designers to make different decisions when they draw layout in these new design rules.
In contrast to leaf cell compaction tools, leaf cell synthesis tools have the capability to generate a new leaf cell layout based upon a transistor-level netlist that specifies the size of transistors and the electrical connections between the transistors. Because a layout synthesis system does not need to maintain an existing layout structure, it can take full advantage of the design rules or circuit requirements, e.g. by reordering transistors, placing transistors in alternating rows, or reallocating routing where resources become available. Many layout synthesis systems use compaction as a final step in generating a layout, but they can still generate more compact layouts than their counterparts that only compact existing layouts.
Most IC layout design tools generate an internal representation of the polygons contained in a layout. Two approaches for representing polygons in an IC layout include the general polygon approach and the wire or path approach.
The general polygon approach uses a single list of points that represents rectangles or trapezoids used to construct the polygons contained in an IC layout. Each rectangle or trapezoid has parallel sides with the same orientation and is defined by four points. Complex polygons are represented by placing multiple trapezoids adjacent to each other. The general polygon approach is arbitrary and provides the flexibility to represent any layout geometry. There is no preferred orientation or "winding direction" in the trapezoids. That is, a trapezoid is not referenced with respect to a particular corner and the sides of a trapezoid are not ordered e.g. with respect to current flow. However, the arbitrary nature makes the general polygon approach difficult to implement in software. Because most synthesis software limits the number of points that can be contained in a single polygon, some complex polygons containing numerous trapezoids must be fractured into smaller polygons. The need to fracture a polygon into many trapezoids or rectangles obscures its purpose, and it is difficult to determine useful properties such as resistance or transistor device size. Also, relatively simple changes in the polygons can result in wholesale restructuring of the trapezoid representation. Many tools use only rectangles because the algorithms required to manipulate non-orthogonal geometry built from trapezoids are complex. Large quantities of trapezoids or rectangles are required to represent all but the simplest polygons, and useful operations like inserting a bend in a wire are difficult because they have no direct analog in a list of concatenated trapezoids. Finally, some implementations of the general polygon approach represent the entire design space, including any unused space between polygons, which increases the polygon count and requires more data to represent the layout.
The wire or path approach represents polygons using a center line and a polygon width for each point along the center line. The simplicity of this approach is easily implemented in synthesis tools and can simplify routing between diffusion islands. Also, the width and resistance of a path can be easily calculated. Most layout geometry can be represented without concatenating wires or placing wires next to each other, and this approach is used in many routing tools. However, the path approach requires that polygons have parallel sides, which makes it unsuitable for more complex shapes, such as octagon-shaped contacts, irregular-shaped diffusion islands, or wires that vary in width.
In view of the need to represent polygons in IC layout synthesis tools and the limitations in existing approaches, an alternative approach for representing polygons in an IC layout is highly desirable.